package MiniSpanTree;

import ch08.MGraph;

public class MiniSpanTree {
    private class CloseEdge{    //内部类辅助记录从顶点集U到V-U的代价最小的边
        Object adjVex;
        int lowCost;
        public CloseEdge(Object adjVex,int lowCost){
            this.adjVex=adjVex;
            this.lowCost=lowCost;
        }
    }
//用普里姆算法从第u个顶点出发构造网的最小生成树T，返回生成树边组成的二维数组

    public Object[][] PRIM(MGraph G0, Object u) throws Exception {
        Object[][] tree0=new Object[G0.getVexNum()-1][2];
        int count=0;
        CloseEdge[] closeEdge=new CloseEdge[G0.getVexNum()];
        int k=G0.locateVex(u);
        for(int j=0;j<G0.getVexNum();j++) //辅助数组初始化
            if(j!=k){

                closeEdge[j]=new CloseEdge(u,G0.getArcs()[k][j]);

            }
        closeEdge[k]=new CloseEdge(u,0); //初始U={u}
        for(int i=1;i<G0.getVexNum();i++){       //选择其余G.vexnum-1个顶点
            k=getMinMum(closeEdge);              //求出T的下一个顶点：第k个顶点
            tree0[count][0]=closeEdge[k].adjVex; //生成树的边放入数组中
            tree0[count][1]=G0.getVexs()[k];
            count++;
            closeEdge[k].lowCost=0;            //第k个顶点并入U集
            for(int j=0;j<G0.getVexNum();j++)  //新顶点并入U后重新选择最小边
                if(G0.getArcs()[k][j]<closeEdge[j].lowCost)
                    closeEdge[j]=new CloseEdge(G0.getVex(k),G0.getArcs()[k][j]);
        }
        return tree0;
    }

    private int getMinMum(CloseEdge[] closeEdge){  //在closeEdge中选出lowCost最小切不为0的顶点
        int min=Integer.MAX_VALUE;
        int v=-1;
        for(int i=0;i<closeEdge.length;i++)
            if(closeEdge[i].lowCost!=0 && closeEdge[i].lowCost<min){
                min=closeEdge[i].lowCost;
                v=i;
            }
        return v;
    }
}
